package middle.code01_window_preprocess;

import lombok.extern.slf4j.Slf4j;

/**
 * 1139. 最大的以 1 为边界的正方形 - 力扣（Leetcode）
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
 * 示例 1：
 * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
 * 示例 2：
 * 输入：grid = [[1,1,0,0]] 输出：1
 *
 * 思路（预处理）
 * 提供了向右连续1的数量，以及向下连续1的数量
 * 加速判断是否形成正方形的查询速度
 */
@Slf4j
public class Code05_LargestBorderedSquare {

    private static int largestBorderedSquare1(int[][] arr) {
        int rows = arr.length;
        int cols = arr[0].length;
        int ans = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                for (int border = 1; border <= Math.min(rows - row, cols - col); border++) {
                    ans = checkSquare1(arr, col, border, row) ? Math.max(ans, border) : ans;
                }
            }
        }
        return ans;
    }

    private static boolean checkSquare1(int[][] arr, int col, int border, int row) {
        // row, col++
        for (int i = col; i < col + border; i++) {
            if (arr[row][i] == 0) {
                return false;
            }
        }
        // row + border -1, col++
        for (int i = col; i < col + border; i++) {
            if (arr[row + border - 1][i] == 0) {
                return false;
            }
        }
        // col, row++
        for (int i = row; i < row + border; i++) {
            if (arr[i][col] == 0) {
                return false;
            }
        }
        // col + border -1, row++
        for (int i = row; i < row + border; i++) {
            if (arr[i][col + border - 1] == 0) {
                return false;
            }
        }
        return true;
    }

    private static int largestBorderedSquare2(int[][] arr) {
        int rows = arr.length;
        int cols = arr[0].length;
        int[][] right = new int[rows][cols];
        int[][] down = new int[rows][cols];
        for (int row = 0; row < rows; row++) {
            for (int col = cols - 1; col >= 0; col--) {
                if (arr[row][col] == 1) {
                    right[row][col] = col + 1 < cols ? 1 + right[row][col + 1] : 1;
                } else {
                    right[row][col] = 0;
                }
            }
        }
        for (int col = 0; col < cols; col++) {
            for (int row = rows - 1; row >= 0; row--) {
                if (arr[row][col] == 1) {
                    down[row][col] = row + 1 < rows ? 1 + down[row + 1][col] : 1;
                } else {
                    down[row][col] = 0;
                }
            }
        }
        int ans = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                for (int border = 1; border <= Math.min(rows - row, cols - col); border++) {
                    if (right[row][col] >= border
                            && down[row][col] >= border
                            && right[row + border - 1][col] >= border
                            && down[row][col + border - 1] >= border
                    ) {
                        ans = Math.max(ans, border);
                    }
                }
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 1, 1},
                {0, 1, 0, 0, 1},
                {0, 1, 0, 0, 1},
                {0, 1, 1, 1, 1},
                {0, 1, 0, 0, 1}};
        log.info("{}", largestBorderedSquare1(arr));
        log.info("{}", largestBorderedSquare2(arr));
    }
}
